// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-25 11:40
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.ArraysTrain.preFixTrain;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class CountTriplets {
    /**
     * 返回异或数量相等的三元组: 二进制枚举 + 前缀和
     */
    public int countTripletsT(int[] arr) {
        int n = arr.length, res = 0;
        /*-----构造前缀和数组-----*/
        int[] preFix = new int[n];
        preFix[0] = arr[0];
        for (int i = 1; i < n; i++) {
            preFix[i] = preFix[i - 1] ^ arr[i];
        }
        /*-----暴力枚举三元组-----*/
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                for (int k = j; k < n; k++) {
                    if (j == i) {
                        j += 1;
                    }
                    int a = getXOR(i, j - 1, preFix), b = getXOR(j, k, preFix);
                    if (a == b) {
                        res++;
                    }
                }
            }
        }
        return res;
    }


    /*-----使用Hash存储已经保存的区域数据-----*/
    public int countTriplets(int[] arr) {
        int n = arr.length;
        // 事实上，甚至可以不预处理「前缀异或数组」，使用一个变量 xor 边遍历边计算即可
        int xor = 0, ans = 0;
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int k = 0; k <= n; k++) {
            if (k >= 1) {
                xor ^= arr[k - 1];
            }
            List<Integer> list = map.getOrDefault(xor, new ArrayList<>());
            for (int idx : list) {
                int i = idx + 1;
                ans += k - i;
            }
            list.add(k);
            map.put(xor, list);
        }
        return ans;
    }


    private int getXOR(int start, int end, int[] preFix) {
        if (start > 0) {
            return preFix[end] ^ preFix[start - 1];
        } else {
            return preFix[end];
        }
    }


    @Test
    public void shout() {
        int[] test = {2, 3, 1, 6, 7};
        System.out.println(countTriplets(test));
    }
}
